home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Power Programmierung
/
Power-Programmierung (Tewi)(1994).iso
/
magazine
/
drdobbs
/
1989
/
09
/
peterson.lst
< prev
next >
Wrap
File List
|
1989-07-27
|
13KB
|
434 lines
_SETTING PRECEDENCE_
by Mark C. Peterson
[LISTING ONE]
/* SPARRAY.H - Header file for SPARRAY.C */
/* Copyright (C) 1988, Mark C. Peterson */
#ifndef SPARRAY_H
#define SPARRAY_H
union VARIABLE {
long Num;
void *Ptr;
};
typedef struct _SPELEM {
struct _SPELEM *Higher, *Lower;
unsigned long Loc;
union VARIABLE Element;
} SPELEM;
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* Loc The location of the element within the sparse array. *
* Higher A pointer to a SPELEM with a higher "Loc" of a lower *
* precedence. *
* Lower A pointer to a SPELEM with a lower "Loc" of a lower *
* precedence. *
* Element A union VARIABLE for storage of either a "long" or "void*" *
* element. "Element" is initialize to a NULL (either 0L or *
* (void*)0) by MakeSpArray() or when an element is removed by *
* RemoveSpElem(). *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
typedef struct _SPARRAY {
SPELEM *SpElem, *Root, *EmptyElem;
unsigned Size, ElemUsed, HighestUsed;
} SPARRAY;
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* SpElem An array of SPELEM structures. The number of SPELEM *
* structures in the array is stored in "Size". *
* Root A pointer to an SPELEM structure that is the root to the *
* Ptree. *
* EmptyElem A pointer to a chain of SPELEM structures (along the *
* "Higher" pointer) that has been removed from the sparse *
* array. *
* Size The number of SPELEM structures in SpElem array. *
* ElemUsed Keeps track of the number of elements in the sparse array. *
* "ElemUsed" should be checked by the programmer periodically *
* to see if the sparse array is full (i.e "ElemUsed" == *
* "Size"). *
* HighestUsed Used by PlaceElement(). If there are no empty elements *
* ("EmptyElem" == NULL) and "HighestUsed" == "Size" the *
* function returns a NULL. *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* Note that the only variable that should be changed directly by the *
* programmer is the "Element" member in the SPELEM structure. *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
SPARRAY *MakeSpArray(unsigned NumElem);
/* Creates the SPARRAY structure with "NumElem" number of elements,
initializes all the elements to zero, and returns a pointer to the
SPARRAY structure. */
SPELEM *FindSpElem(SPARRAY *Array, unsigned long Loc);
/* Returns a pointer to the SPELEM structure associated with "Loc".
if "Loc" is not in the sparse array the function returns a NULL. */
SPELEM *PlaceSpElem(SPARRAY *Array, unsigned long Loc);
/* Places the "Loc" in the Ptree structure. Returns a NULL if the sparse
array is full.
WARNING: This function should only be called if FindElement() returns
a NULL. Attempts to place a "Loc" that is already there will corrupt
the Ptree. */
SPELEM *SpArray(SPARRAY *Array, unsigned long Loc);
/* Attempts to locate "Loc" using FindElement(). If not found the "Loc"
is placed using PlaceElement(). Returns a NULL if "Loc" is not found
and the sparse array is full. */
void ClrSpArray(SPARRAY *Array);
/* Removes all the elements from the sparse array. */
void DeleteSpArray(SPARRAY **ArrayRef);
/* Frees the memory allocated by MakeSpArray and sets the SPARRAY pointer
referenced by ArrayRef to NULL. */
void RemoveSpElem(SPARRAY *Array, unsigned long Loc);
/* Removes "Loc" from the sparse array. */
#endif
[LISITNG TWO]
/* SPARRAY.C - Routines for maintaining a sparse array using a Ptree */
/* Copyright (C) 1988, Mark C. Peterson */
#include <stdlib.h>
#include "SPARRAY.H"
static SPELEM
*PruneLower(SPELEM *this, unsigned long Loc),
*PruneHigher(SPELEM *this, unsigned long Loc);
static unsigned
ChkPrecGT(unsigned long Loc, unsigned long ThisLoc);
/* Check "Loc" precedence greater than "ThisLoc" precedence. */
SPARRAY *MakeSpArray(unsigned NumElem) {
SPARRAY *Array;
if(Array = calloc(1, sizeof(SPARRAY))) {
Array->Size = NumElem;
if(!(Array->SpElem = (SPELEM*)calloc(NumElem, sizeof(SPELEM)))) {
free(Array);
Array = (SPARRAY*)0;
}
}
return(Array);
}
static SPELEM *PruneLower(SPELEM *this, unsigned long Loc) {
SPELEM *RetPtr;
while(this->Lower && (this->Lower->Loc > Loc)) this = this->Lower;
if(RetPtr = this->Lower) this->Lower = PruneHigher(this->Lower, Loc);
return(RetPtr);
}
static SPELEM *PruneHigher(SPELEM *this, unsigned long Loc) {
SPELEM *RetPtr;
while(this->Higher && (this->Higher->Loc < Loc))
this = this->Higher;
if(RetPtr = this->Higher) this->Higher = PruneLower(this->Higher, Loc);
return(RetPtr);
}
static unsigned ChkPrecGT(unsigned long Loc, unsigned long ThisLoc) {
unsigned long LocPrec, ThisPrec;
while(Loc && ThisLoc) {
LocPrec = (Loc - 1) ^ Loc;
ThisPrec = (ThisLoc - 1) ^ ThisLoc;
if(LocPrec != ThisPrec) return(LocPrec > ThisPrec);
Loc >>= 1;
ThisLoc >>= 1;
}
return(Loc > ThisLoc);
}
SPELEM *PlaceSpElem(SPARRAY *Array, unsigned long Loc) {
SPELEM **this, *New;
/* This section sets up a "New" SPELEM pointer */
if(!Array->EmptyElem) {
if(Array->HighestUsed < Array->Size)
New = &Array->SpElem[Array->HighestUsed++];
else return((SPELEM*)0);
}
else {
New = Array->EmptyElem;
Array->EmptyElem = Array->EmptyElem->Higher;
}
Array->ElemUsed++;
New->Higher = New->Lower = (SPELEM*)0;
New->Loc = Loc;
/* This section places the "New" SPELEM pointer into the Ptree */
this = &Array->Root;
while(*this) {
if(ChkPrecGT(Loc, (*this)->Loc)) {
if((*this)->Loc > Loc) {
New->Higher = *this;
New->Lower = PruneLower(*this, Loc);
}
else {
New->Lower = *this;
New->Higher = PruneHigher(*this, Loc);
}
break;
}
else this = (*this)->Loc > Loc ? &(*this)->Lower : &(*this)->Higher;
}
*this = New;
return(*this);
}
void RemoveSpElem(SPARRAY *Array, unsigned long Loc) {
SPELEM *Hole, *HigherInter, *LowerInter, **this;
/* Find the element to be removed */
this = &Array->Root;
while(*this && ((*this)->Loc != Loc))
this = (*this)->Loc > Loc ? &(*this)->Lower : &(*this)->Higher;
if(Hole = *this) {
/* Fill the hole in the Ptree if the element was found */
LowerInter = Hole->Lower; /* Lower Interface Pointer */
HigherInter = Hole->Higher; /* Higher Interface Pointer */
while(LowerInter && HigherInter) {
if(ChkPrecGT(LowerInter->Loc, HigherInter->Loc)) {
*this = LowerInter;
this = &LowerInter->Higher;
LowerInter = LowerInter->Higher;
}
else {
*this = HigherInter;
this = &HigherInter->Lower;
HigherInter = HigherInter->Lower;
}
}
if(LowerInter) *this = LowerInter;
else *this = HigherInter;
/* Link the unused spot into the chain of empty elements along
the "Higher" linkage. */
Hole->Higher = Array->EmptyElem;
Array->EmptyElem = Hole;
Array->ElemUsed--; /* Update the number of elements used */
}
}
SPELEM *FindSpElem(SPARRAY *Array, unsigned long Loc) {
SPELEM *this;
this = Array->Root;
while(this && (this->Loc != Loc))
this = this->Loc > Loc ? this->Lower : this->Higher;
return(this);
}
SPELEM *SpArray(SPARRAY *Array, unsigned long Loc) {
SPELEM *Found;
Found = FindSpElem(Array, Loc);
if(!Found)
Found = PlaceSpElem(Array, Loc);
return(Found);
}
void ClrSpArray(SPARRAY *Array) {
unsigned n;
Array->EmptyElem = Array->Root = (SPELEM*)0;
for(n = 0; n < Array->Size; n++)
Array->SpElem[n].Element.Num = 0L;
Array->HighestUsed = Array->ElemUsed = 0;
}
void DeleteSpArray(SPARRAY **ArrayRef) {
SPARRAY *Array;
if(Array = *ArrayRef) {
free(Array->SpElem);
free(Array);
*ArrayRef = (SPARRAY*)0;
}
}
[LISTING THREE]
/* DIAGARRA.H - Header file for DIAGARRA.C */
/* Copyright (C) 1988, Mark C. Peterson */
#ifndef DIAGARRA_H
#define DIAGARRA_H
#include "SPARRAY.H"
extern unsigned MaxTrav, NumElem, NumLines;
extern unsigned long TotalTrav;
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* MaxTrav - Maximum number of traversals from the root to any *
* number in the Ptree, set by SumSpArray(). *
* NumElem - Number of elements in the Ptree, set by SumSpArray(). *
* NumLines - Number of lines printed, set by DiagSpArray(). *
* TotalTrav - Total number of linkages in the Ptree, set by *
* SumSpArray(). *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
void DiagSpArray(SPARRAY *this);
/* Diagram the Ptree used by the SPARRAY */
void DumpSpArray(SPELEM *this);
/* Dump an ordered listing of the elements of the SPARRAY */
void SumSpArray(SPARRAY *Array);
/* Determine various statistics about the Ptree used by the SPARRAY */
#endif
[LISTING FOUR]
/* DIAGARRA.C - Routines for diagraming the Ptree of a SPARRAY */
/* Copyright (C) 1988, Mark C. Peterson */
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include "DIAGARRA.H"
static char String[8000];
unsigned MaxTrav, NumElem, NumTrav, StrLength, NumLines;
unsigned long TotalTrav;
static void RecDiagSpArray(SPELEM *this) {
unsigned NumLength;
NumLength = printf("%ld", this->Loc);
if(this->Higher) strcat(String, "| ");
else strcat(String, " ");
StrLength += 2;
memset(String + StrLength, ' ', NumLength);
StrLength += NumLength;
String[StrLength] = '\0';
if(this->Lower) {
printf("--");
RecDiagSpArray(this->Lower);
}
StrLength -= (NumLength + 2);
if(this->Higher) {
printf("\n%s\n", String);
NumLines++;
String[StrLength] = '\0';
printf("%s", String);
RecDiagSpArray(this->Higher);
}
else String[StrLength] = '\0';
}
void DiagSpArray(SPARRAY *Array) {
String[0] = '\0';
NumLines = StrLength = 0;
if(Array->Root) RecDiagSpArray(Array->Root);
else printf("<NULL>");
}
void DumpSpArray(SPELEM *this) {
if(this->Lower) DumpSpArray(this->Lower);
printf("%lu\t", this->Loc);
if(this->Higher) DumpSpArray(this->Higher);
}
static void RecSumSpArray(SPELEM *this) {
NumElem++;
if(NumTrav > MaxTrav) MaxTrav = NumTrav;
TotalTrav += (long)NumTrav;
if(this->Lower) {
NumTrav++;
RecSumSpArray(this->Lower);
NumTrav--;
}
if(this->Higher) {
NumTrav++;
RecSumSpArray(this->Higher);
NumTrav--;
}
}
void SumSpArray(SPARRAY *Array) {
MaxTrav = NumElem = NumTrav = 0;
TotalTrav = 0l;
RecSumSpArray(Array->Root);
}
[LISTING FIVE]
/* PTREE.C - Program for constructing and diagraming a Ptree */
/* Copyright (C) 1988, Mark C. Peterson */
#include <stdio.h>
#include <stdlib.h>
#include "SPARRAY.H"
#include "DIAGARRA.H"
#define INPUT_SIZE 15
#define ARRAY_SIZE 100
char *InputNum(char *Input, unsigned size) {
static char PromptStr[] = "\n\nNumber? ";
printf(PromptStr);
return(fgets(Input, size, stdin));
}
void main(void) {
char Input[INPUT_SIZE];
SPARRAY *Array;
unsigned long Number;
if(Array = MakeSpArray(ARRAY_SIZE)) {
puts("Enter a number at the prompt. If it is not in the");
puts("Ptree it will be added. If the number is in the");
puts("Ptree it will be deleted. To end the program enter a");
puts("blank line.\n");
while(*InputNum(Input, INPUT_SIZE - 1) != '\n') {
putchar('\n');
Number = atol(Input);
if(FindSpElem(Array, Number)) RemoveSpElem(Array, Number);
else {
if(!PlaceSpElem(Array, Number)) {
puts("Array Full");
break;
}
}
DiagSpArray(Array);
}
DeleteSpArray(&Array);
}
else puts("Error making SpArray");
}